package com.code.leetcode.idea;

/**
 * https://blog.csdn.net/sjp11/article/details/124366179
 *
 * TODO 添加动态规划
 */
public class LeetCodeIdea005_02 {
    public static void main(String[] args) {
        LeetCodeIdea005_02 leetCodeIdea005_02 = new LeetCodeIdea005_02();
        String test = "abcfdafdsafdsafdafdafdafdsfafdsafdsafdafdsafdsafdsafdsafds1212131323214343235454534543645662436436464d";
        String result = leetCodeIdea005_02.longestPalindrome(test);
        System.out.println(result);
    }

    public String longestPalindrome(String s) {
        int left = 0, right = 0;
        int maxLength = 0;
        for (int i = 0; i < s.length(); i++) {
            int subLeft = i, subRight = i;
            while (subRight + 1 < s.length() && s.charAt(i) == s.charAt(subRight+1)) {
                subRight++;
            }
            while (subRight + 1 < s.length() && subLeft - 1 >=0 && s.charAt(subLeft - 1) == s.charAt(subRight + 1)) {
                subRight++;
                subLeft--;
            }
            int length = subRight - subLeft + 1;
            if (length > maxLength) {
                left = subLeft;
                right = subRight;
                maxLength = length;
            }

        }
        return s.substring(left, right+1);
    }

}
